import java.util.Stack;

class Solution {

    //根据前序和中序创建二叉树
    // public int preIndex = 0;
    // public TreeNode buildTree(int[] preorder, int[] inorder) {
    //     return buildTreeChild(preorder,inorder,0,inorder.length-1);
    // }
    // private TreeNode buildTreeChild(int[] preorder, int[] inorder,int inbegin,int inend) {
    //     //递归的出口  不满足这个条件 那么就是没有了左树 或者右树
    //     if(inbegin > inend) {
    //         return null;
    //     }
    //     //先创建根节点
    //     TreeNode root = new TreeNode(preorder[preIndex]);//根节点

    //     //找到根节点 所在中序遍历中的位置
    //     int rootIndex = findIndex(inorder,inbegin,inend,preorder[preIndex]);
    //     preIndex++;
    //     // 先创建左树 再创建右树   本身是在遍历： 前序遍历
    //     root.left = buildTreeChild(preorder,inorder,inbegin,rootIndex-1);
    //     root.right = buildTreeChild(preorder,inorder,rootIndex+1,inend);

    //     return root;
    // }

    // private int findIndex(int[] inorder,int inbegin,int inend,int key) {
    //     for(int i = inbegin; i <= inend; i++) {
    //         if(inorder[i] == key) {
    //             return i;
    //         }
    //     }
    //     return -1;
    // }




    //根据中序和后序遍历建立二叉树
    // public int postIndex = 0;

    // public TreeNode buildTree(int[] inorder, int[] postorder) {

    //     postIndex = postorder.length-1;

    //     return buildTreeChild(postorder,inorder,0,inorder.length-1);
    // }


    // private TreeNode buildTreeChild(int[] postorder, int[] inorder,int inbegin,int inend) {
    //     //递归的出口  不满足这个条件 那么就是没有了左树 或者右树
    //     if(inbegin > inend) {
    //         return null;
    //     }
    //     //先创建根节点
    //     TreeNode root = new TreeNode(postorder[postIndex]);//根节点

    //     //找到根节点 所在中序遍历中的位置
    //     int rootIndex = findIndex(inorder,inbegin,inend,postorder[postIndex]);
    //     postIndex--;
    //     // 先创建右树    再创建左树   本身是在遍历： 后序遍历

    //     root.right = buildTreeChild(postorder,inorder,rootIndex+1,inend);

    //     root.left = buildTreeChild(postorder,inorder,inbegin,rootIndex-1);

    //     return root;
    // }

    // private int findIndex(int[] inorder,int inbegin,int inend,int key) {
    //     for(int i = inbegin; i <= inend; i++) {
    //         if(inorder[i] == key) {
    //             return i;
    //         }
    //     }
    //     return -1;
    // }







    //最近公共祖先,分四种情况
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return null;

        if(p == root || q == root) {
            return root;
        }

        TreeNode leftRet = lowestCommonAncestor(root.left,p,q);//左子树最上层的p或者q
        TreeNode rightRet = lowestCommonAncestor(root.right,p,q);//右子树最上层的p或者q

        if(leftRet != null && rightRet != null) {
            return root;
        }else if(leftRet != null) {
            return leftRet;
        }else {
            return rightRet;
        }
    }



}